package org.hot100_3;

import java.util.ArrayDeque;
import java.util.Deque;

public class leetcode239 {
    public int[] maxSlidingWindow(int[] nums, int k) {

        int n = nums.length;
        // 当窗口移动到最后时，窗口的右边界为n-1,左边界为n-1-(k-1)=n-k
        // 从0到n-k总共有n-k+1个元素。
        int[] res = new int[n - k + 1];
        int index = 0;

        Deque<Integer> deque = new ArrayDeque<>();

        for (int right = 0; right < n; right++) {

            int left = right - k + 1;

            //需要remove操作，需要保证deque不为空
            while (!deque.isEmpty() && deque.peekFirst() < left) {
                deque.removeFirst();
            }

            while (!deque.isEmpty() && nums[right] > nums[deque.peekLast()]) {
                deque.removeLast();
            }

            deque.offer(right);

            if (right >= k - 1) {
                res[index] = nums[deque.getFirst()];
                index++;
            }
        }

        return res;
    }
}
